การลงจุดของลอการิทึมธรรมชาติของแฟกทอเรียล

เมื่อ n มีค่าเพิ่มขึ้น ค่า n! จะมีอัตราการเติบโตมากกว่าพหุนามและฟังก์ชันเลขชี้กำลังทั้งหมดที่มี n ประกอบอยู่ (แต่ก็ยังน้อยกว่าฟังก์ชันเลขชี้กำลังสองชั้น)

การประมาณค่าที่ใกล้เคียงที่สุดของ n! ใช้พื้นฐานบนลอการิทึมธรรมชาติดังนี้

log ⁡ n ! = ∑ x = 1 n log ⁡ x {\displaystyle \log n!=\sum _{x=1}^{n}\log x}

กราฟของฟังก์ชัน f(n) = log n! แสดงไว้ในภาพด้านขวา ลักษณะของกราฟดูเหมือนเป็นเส้นตรง (ฟังก์ชันเชิงเส้น) สำหรับทุกค่าของ n ที่เป็นไปได้ แต่ความจริงมันไม่ใช่เส้นตรง เราอาจประมาณค่า log n! อย่างง่ายโดยกำหนดขอบเขตบนและล่างด้วยปริพันธ์

∫ 1 n log ⁡ x d x ≤ ∑ x = 1 n log ⁡ x ≤ ∫ 0 n log ⁡ ( x + 1 ) d x {\displaystyle \int _{1}^{n}\log x\,dx\leq \sum _{x=1}^{n}\log x\leq \int _{0}^{n}\log(x+1)\,dx}

ซึ่งจะได้การประมาณค่าดังนี้

n log ⁡ ( n e ) + 1 ≤ log ⁡ n ! ≤ ( n + 1 ) log ⁡ ( n + 1 e ) + 1 {\displaystyle n\log \left({\frac {n}{e}}\right)+1\leq \log n!\leq (n+1)\log \left({\frac {n+1}{e}}\right)+1}

เนื่องจากการคำนวณ log n! มีประสิทธิภาพเป็น Θ(n log n) สิ่งนี้จึงมีบทบาทหลักในการวิเคราะห์ความซับซ้อนในการคำนวณของขั้นตอนวิธีการเรียงลำดับ (ดูเพิ่มที่การเรียงลำดับแบบเปรียบเทียบ)

จากขอบเขตของ log n! ที่ได้ สามารถลดรูปจนเหลือเพียง

e ( n e ) n ≤ n ! ≤ e ( n + 1 e ) n + 1 {\displaystyle e\left({\frac {n}{e}}\right)^{n}\leq n!\leq e\left({\frac {n+1}{e}}\right)^{n+1}}

การใช้สูตรดังกล่าวในทางปฏิบัติบางครั้งสามารถประมาณได้ง่ายกว่าแต่ไม่เคร่งครัด สูตรดังกล่าวสามารถแสดงให้เห็นได้ว่า สำหรับทุกค่าของ n จะได้ ( n / 3 ) n < n ! {\displaystyle (n/3)^{n}<n!} และสำหรับ n ≥ 6 จะได้ n ! < ( n / 2 ) n {\displaystyle n!<(n/2)^{n}} เป็นต้น

เมื่อ n เป็นจำนวนขนาดใหญ่ เรามีวิธีการประมาณค่า n! ที่ดีกว่าโดยใช้การประมาณของสเตอร์ลิง (Stirling's approximation)

n ! ≈ 2 π n ( n e ) n {\displaystyle n!\approx {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}}

ในความเป็นจริง สำหรับทุกค่าของ n สูตรดังกล่าวสามารถพิสูจน์ได้ว่า

n ! > 2 π n ( n e ) n {\displaystyle n!>{\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}}

การประมาณค่า log n! ที่ดีกว่าอีกสูตรหนึ่ง กำหนดไว้โดย ศรีนิวาสะ รามานุจัน ดังนี้ [4]

log ⁡ n ! ≈ n log ⁡ n − n + log ⁡ ( n ( 1 + 4 n ( 1 + 2 n ) ) ) 6 + log ⁡ ( π ) 2 {\displaystyle \log n!\approx n\log n-n+{\frac {\log(n(1+4n(1+2n)))}{6}}+{\frac {\log(\pi )}{2}}}